/**
 * @ClassName SalesMan
 * @Description TODO
 * @Author Quentin_zyj
 * @Date 2021/11/3 19:26
 */
public class SalesMan {

    // 图G的顶点数
    static int n;
    // 当前解
    static int[] x;
    // 当前最优解
    static int[] bestx;
    // 图G的邻接矩阵
    static int[][] a;
    // 当前费用
    static int cc;
    // 当前最优值
    static int bestc;
    // 无边标记
    static int noEdge;

    static void back(int i) {
        if (i == n) {
            // 如果城市x[n-1]到城市x[n]有边 && 城市x[n]到城市1有边 && (当前费用 + 城市x[n-1]到城市x[n]的费用 + 城市x[n]到城市1的费用小于当前最优解 || 没有当前最优解)
            if (a[x[n - 1]][x[n]] != noEdge && a[x[n]][1] != noEdge &&
                    (cc + a[x[n - 1]][x[n]] + a[x[n]][1] < bestc || bestc == noEdge)) {
                for (int j = 1; j <= n; j++) {
                    // 记录最优解
                    bestx[j] = x[j];
                }
                // 记录最优值
                bestc = cc + a[x[n - 1]][x[n]] + a[x[n]][1];
            }
        } else {
            for (int j = i; j <= n; j++) {
                // 是否可进入x[j]子树
                if (a[x[i - 1]][x[j]] != noEdge && (cc + a[x[i - 1]][x[j]] < bestc || bestc == noEdge)) {
                    // 搜索子树
                    swap(x, i, j);
                    cc += a[x[i - 1]][x[j]];
                    back(i + 1);
                    cc -= a[x[i - 1]][x[j]];
                    swap(x, i, j);
                }
            }
        }
    }

    static void swap(int[] a, int i, int j) {
        a[i] += a[j];
        a[j] = a[i] - a[j];
        a[i] = a[i] - a[j];
    }
}
